0% completed
Problem Statement
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made.
Examples
-
- Input:
s = "abccba" - Output:
"" - Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
- Input:
-
- Input:
s = "foobar" - Output:
"fbar" - Explanation: We remove "oo" to get "fbar".
- Input:
-
- Input:
s = "fooobar" - Output:
"fobar" - Explanation: We remove the pair "oo" to get "fobar".
- Input:
-
- Input:
s = "abcd" - Output:
"abcd" - Explanation: No adjacent duplicates so no changes.
- Input:
Constraints:
- 1 <= s.length <= 105
sconsists of lowercase English letters.
Solution
This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.
Algorithm Walkthrough
- Initialize an empty stack.
- Loop through the characters in the given string
s. - For each character:
- If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
- Otherwise, push the current character onto the stack.
- Finally, build the result string from the characters remaining on the stack.
Code
Here is the code for this algorithm:
Time and Space Complexity
The time complexity of this algorithm is s, because we perform one operation per character in s. The space complexity is also
On this page
Problem Statement
Solution
Code
Time and Space Complexity